package LeetCode算法;

/**
 * 先存在两个链表：
 *      2 -> 4 -> 3
 *      5 -> 6 -> 4
 * 求他们的和
 *      7 -> 0 -> 4
 * 因为2+5等于7，4+6=10，可以向后进一位，3+4原本为7，但是前面4+6为10，可以得到进一位的机会，所以是3+4+1等于8
 *
 * 可采用链表的形似
 */
public class 两个单链表求和 {

}


class ListNode{
    int val;
    ListNode next;
    ListNode(int x){val = x;}

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2){
        ListNode dummyHead = new ListNode(0);//初始化节点头，但不储存内容，后续curr指向节点头，通过操作curr的方式操作这个节点头
        ListNode p = l1, q = l2, curr = dummyHead;//通过创建临时变量去简介操作两个链表
        int carry = 0;//初始化进位为0
        while (p != null || q != null){//当当前临时变量所指向的链表节点不为null，就意味着改链表还有内容读取
            int x = (p != null) ? p.val : 0;//当前节点不为null就代表还有元素，继续使用，为null则转换为0
            int y = (q != null) ? p.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;//判断两个链表当前节点是否存在相加大于10，如果大于是就进一位，不大于就不做操作
            curr.next = new ListNode(sum % 10);//将两节点的和创建新的节点
            curr = curr.next;//将curr变成下一个节点，好接受下一个和
            if (p != null) p = p.next;//如果当前节点不为null则跳转至下一个
            if (q != null) q = q.next;
        }
        if (carry > 0) curr.next = new ListNode(carry);//如果说最后一次节点相加仍大于10，则最后结果会是链表长度+1个元素

        return dummyHead.next;
    }
}
